/*
 * @Author: liusheng
 * @Date: 2022-06-29 22:16:12
 * @LastEditors: liusheng
 * @LastEditTime: 2022-06-29 22:50:51
 * @Description: 剑指 Offer II 092. 翻转字符
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 092. 翻转字符
如果一个由 '0' 和 '1' 组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是 单调递增 的。

我们给出一个由字符 '0' 和 '1' 组成的字符串 s，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。

返回使 s 单调递增 的最小翻转次数。

 

示例 1：

输入：s = "00110"
输出：1
解释：我们翻转最后一位得到 00111.
示例 2：

输入：s = "010110"
输出：2
解释：我们翻转得到 011111，或者是 000111。
示例 3：

输入：s = "00011000"
输出：2
解释：我们翻转得到 00000000。
 

提示：

1 <= s.length <= 20000
s 中只包含字符 '0' 和 '1'
 

注意：本题与主站 926 题相同： https://leetcode-cn.com/problems/flip-string-to-monotone-increasing/

通过次数11,221  提交次数16,619
 */

#include "header.h"

/*
了解 动态规划 过程助力完成解题思路分析
定义：动态规划要解决的都是一些问题的最优解，即从很多解决问题的方案中找到最优的一个。
过程：当求一个问题最优解的时候，如果可以把问题分解成多个子问题，然后递归地找到每个子问题的最优解，最后通过一定的数学方法对各个子问题的最优解进行组合得出最终的结果。
总结来说就是一个问题的最优解是由它的各个子问题的最优解决定的。将子问题的解进行组合可以得到原问题的解是动态规划可行性的关键。

首先读懂题意，要通过翻转01把整个序列变为0在前1在后，那么我们可以在序列中找到一个点，这个点之前的1全部翻转为0，
这个点之后的0全部翻转为1使得总翻转次数最小。
定义变量num1来记录当前点以前1的个数，ans记录当前最小翻转次数。
从0到n-1遍历整个序列

如果当前位置为1，将num1+1记录
如果当前位置为0，判断是将前面的1翻转为0次数少还是将当前点翻转为1次数少，即ans=min(flips,ans+1)
*/
class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int nums1 = 0;
        int minFlip = 0;
        for (int i = 0; i < s.size(); ++i)
        {
            //current is '1',do not need flip
            if (s[i] == '1')
            {
                ++nums1;
            }
            else
            {
                //minFlip is min of prev 1 num and
                //prev minFlip + 1
                minFlip = min(nums1,minFlip + 1);
            }
        }
        
        return minFlip;
    }
};
